1. Field
Embodiments of the invention relate to the field of networking; and more specifically, to computing a constraint based path.
2. Background
Constraint based path computation processes paths based on one or more constraints. For example, a network administrator may use constraint based path computation to select a path from a source to a destination in a given network based on one or more constraints. In the network, the characteristics of the links (e.g., cost, available bandwidth, link color, etc.) are propagated throughout the network using link-state routing protocols (e.g., Open Shortest Path First (OSPF) (described in Request For Comments (RFC) 2328, “OSPF Version 2”, April 1998), Intermediate System to Intermediate System (IS-IS) (described in International Standard ISO/IEC 10589:2002E, Nov. 15, 2002)). Typically these characteristics are stored in a traffic engineering database on each network element in the network. Thus, the traffic engineering database stores a representation of the topology of the network. A network element may receive a service request for a path to a destination (thus this network element is the source of the path) with one or more constraints (e.g., a network administrator, using a command line interface (CLI), requests a path to a destination given one or more constraints). The network element computes the requested path based on the constraints and the information in the traffic engineering database.
For example, the request may include one or more exclusion constraints that require the path not go through certain network elements or certain links. Typically, during path computation, each network element or link in the network is compared to the list of exclusion constraints to determine if that network element or link should be excluded. Thus, if there are many exclusion constraints, multiple comparisons are made for each network element and/or link in the network (e.g., one comparison for each constraint on the list).
After a path has been computed, that path can be re-optimized. For example, after a path has been computed and the path has been assigned a certain amount of bandwidth, a network administrator may want to see if that path can be re-optimized, for example, with a bigger amount of bandwidth. There may be numerous reasons why a better path and/or better path characteristics (e.g., higher available bandwidth) exist in the network compared to the computed path. For example, if a network element joined the network after the path was originally computed, a better path and/or better path characteristics may exist. As another example, the characteristics of the links of the path may change over time (e.g., they may have more available bandwidth at a later time). During path re-optimization, the currently allocated bandwidth of the links of the calculated paths is taken into account. For example, if the path had reserved a bandwidth of 50 (e.g., each link has a currently allocated bandwidth of 50), that allocation is taken into account when processing the re-optimization request.
Typically, during path re-optimization, each link in the network is compared to the links of the calculated path to determine whether to take into account the currently allocated bandwidth of that link. Thus, if there are many links in the calculated path, multiple comparisons are made for each link in the network (e.g., one comparison for each link in the path).